/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-11-15
 * Time: 10:11
 */
import java.util.ArrayList;
import java.util.List;

public class MaximumClique {
    private int maxSize; // 最大团的顶点数量
    private List<Integer> maxClique; // 最大团的顶点集合

    public List<Integer> findMaximumClique(int[][] graph) {
        int n = graph.length;
        maxSize = 0;
        maxClique = new ArrayList<>();
        List<Integer> currentClique = new ArrayList<>(); // 当前正在构建的团

        // 从第0个顶点开始回溯
        backtrack(graph, 0, currentClique);
        return maxClique;
    }

    // 回溯函数：尝试将顶点v加入当前团，或不加入
    private void backtrack(int[][] graph, int v, List<Integer> currentClique) {
        int n = graph.length;

        // 终止条件：所有顶点都处理完了
        if (v == n) {
            // 更新最大团（如果当前团更大）
            if (currentClique.size() > maxSize) {
                maxSize = currentClique.size();
                maxClique = new ArrayList<>(currentClique); // 复制当前团
            }
            return;
        }

        // 检查顶点v是否能加入当前团（与团中所有顶点都相连）
        boolean canAdd = true;
        for (int u : currentClique) {
            // 若v和u之间没有边，则不能加入
            if (graph[v][u] == 0) {
                canAdd = false;
                break;
            }
        }

        // 选择1：加入顶点v（如果可以）
        if (canAdd) {
            currentClique.add(v);
            backtrack(graph, v + 1, currentClique); // 递归处理下一个顶点
            currentClique.remove(currentClique.size() - 1); // 回溯：移除v
        }

        // 选择2：不加入顶点v（即使能加入，也尝试不选的情况）
        // 剪枝优化：如果剩余顶点数 + 当前团大小 <= 已有最大团，就没必要继续了
        if (currentClique.size() + (n - v - 1) > maxSize) {
            backtrack(graph, v + 1, currentClique);
        }
    }

    public static void main(String[] args) {
        // 示例图：邻接矩阵表示（graph[i][j] = 1 表示顶点i和j相连，0表示不相连）
        // 顶点0-4的图：0-1, 0-2, 1-2, 1-3, 2-3, 3-4 有边
        int[][] graph = {
                {0, 1, 1, 0, 0}, // 顶点0：与1、2相连
                {1, 0, 1, 1, 0}, // 顶点1：与0、2、3相连
                {1, 1, 0, 1, 0}, // 顶点2：与0、1、3相连
                {0, 1, 1, 0, 1}, // 顶点3：与1、2、4相连
                {0, 0, 0, 1, 0}  // 顶点4：与3相连
        };

        MaximumClique solver = new MaximumClique();
        List<Integer> maxClique = solver.findMaximumClique(graph);

        System.out.println("最大团的顶点数量：" + maxClique.size());
        System.out.println("最大团的顶点（索引）：" + maxClique); // 输出 [1,2,3]（大小为3）
    }
}
